package com.xiaoxu.entry.bishi;

import java.util.HashMap;

public class 爬楼梯 {
    public static void main(String[] args) {
        System.out.println("啦楼梯");
        int digui = digui(6);
        System.out.println("可能次数： " + digui);
        int byMap = diguiByMap(6);
        System.out.println("map: " +byMap);
        int sum = sum(6);
        System.out.println("sum: " + sum);
    }

    /**
     * 方法一、递归暴力解法  时间复杂度高 o(n^)
     */
    public static int digui(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;
        return digui(n-1)+digui(n-2);
    }

    static HashMap<Integer, Integer> map = new HashMap<>();
    /**
     * 方法2 引入hashMap
     *
     */
    public static int diguiByMap(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (map.get(n) != null){
            return map.get(n);
        }else {
            int result = diguiByMap(n - 1) + diguiByMap(n - 2);
            map.put(n,result);
            return result;
        }
    }

    /**
     * 方法三  循环解法 自底向上累加
     */
    public static int sum(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;
        int result  = 0;
        int preTow = 1;//n 的前两次的次数  重第三层开始 n=1
        int preOne = 2;//n 的前一次的次数  重第三层开始 n=2
        for (int i=3;i<=n;i++){
            result = preOne + preTow;
            preTow = preOne;
            preOne = result;
        }
        return result;
    }
}
